package code1.stack_and_queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 原题链接：https://leetcode.cn/problems/sliding-window-maximum/
 */
public class P239 {

    //定义一个单调队列(出口元素最大，单调递减)来维护滑动窗口，保证窗口每次弹出的元素都是最大值
    //滑动窗口移动时，移除最前面的元素，加入最后面的元素
    class MyQueue{
        //用双端队列来实现
        Deque<Integer> deque=new LinkedList<>();

        //弹出指定元素
        //如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
        void poll(int val){
            if(!deque.isEmpty() && deque.getFirst()==val){
                deque.pollFirst();
            }
        }

        //加入指定元素
        //如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
        void push(int val){
            while(!deque.isEmpty() && val>deque.getLast()){
                deque.pollLast();
            }
            deque.addLast(val);
        }

        //获取出口元素，即当前窗口中的最大值
        int peek(){
            return deque.getFirst();
        }
    }

    //单调队列法，时间复杂度为O(n)
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if(nums.length==1){
            return nums;
        }
        int[] res=new int[nums.length-k+1];
        int index=0;
        MyQueue queue=new MyQueue();
        //将第一个窗口中的元素加入队列中
        for(int i=0;i<k;i++){
            queue.push(nums[i]);
        }
        res[index++]=queue.peek();
        //开始移动窗口
        for(int i=k;i<nums.length;i++){
            //移除开头元素
            queue.poll(nums[i-k]);
            //在末尾加入新元素
            queue.push(nums[i]);
            //获取当前窗口的最大值
            res[index++]=queue.peek();
        }
        return res;
    }


    //暴力法，时间复杂度为O(n*k)，不出意外的爆了
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res=new int[nums.length-k+1];
        int count=0;
        for(int i=0;i+k-1<nums.length;i++){
            int max=-10000;
            for(int j=i;j<=i+k-1;j++){
                max=Math.max(max,nums[j]);
            }
            res[count++]=max;
        }
        return res;
    }


}
